package com.example.leetcode;

import java.util.*;

public class TreeSelect {
    public static List<Integer> preOrder(TreeNone none){
        List<Integer> noneList = new ArrayList<>();

        if (none==null){
            return null;
        }

        List<Integer> left= preOrder(none.left);
        List<Integer> right=preOrder(none.right);
        noneList.add(none.val);
        noneList.addAll(left);
        noneList.addAll(right);


        return noneList;
    }
    public static List<Integer> preOrder1(TreeNone root){
        List<Integer> result = new ArrayList<>();

        if (root==null){
            return null;
        }
        //定义一个栈
        Stack<TreeNone> stack = new Stack<>();
        //将树全部压到栈里
        stack.push(root);
        //判断栈是否为空如果是空就跳出
        while (!stack.isEmpty()){
            //弹出跟节点
            TreeNone none=stack.pop();
            result.add(none.val);
            //先将右子树压入栈 （栈是先进后出的）
            if (none.right!=null){
                stack.push(none.right);
            }
            //将左子树压入栈
            if (none.left!=null){
                stack.push(none.left);
            }
        }



        return result;
    }


    public static List<Integer> inOrder(TreeNone none){
      List<Integer> list = new ArrayList<>();
        if (none==null){
          return null;
            }
        List<Integer> left= inOrder(none.left);
        List<Integer> right= inOrder(none.right);
        list.addAll(left);
        list.add(none.val);
        list.addAll(right);
        return list;
    }



    public static List<Integer> inOrder1(TreeNone root){
        List<Integer> result = new ArrayList<>();
        if (root==null){
            return null;
        }
        //新建一个栈
        Stack<TreeNone> stack= new Stack<>();
        //根节点
        TreeNone current=root;
        while (current!=null || !stack.isEmpty()){
            while (current!=null){
//                压入当前值
                stack.push(current);
                //将改节点左子树付给当前值
                current=current.left;
            }
            //弹出
            current=stack.pop();
            result.add(current.val);
            //将节点右子树付给当前值
            current=current.right;
        }


        return result;
    }



    public static List<Integer> postOrder(TreeNone none){
        List<Integer> list = new ArrayList<>();
        if (none==null){
            return null;
        }
        List<Integer> left= postOrder(none.left);
        List<Integer> right= postOrder(none.right);
        list.addAll(left);
        list.addAll(right);
        list.add(none.val);
        return list;
    }

    //断子绝孙法
    public static List<Integer> postOrder1(TreeNone root){
        List<Integer> result = new ArrayList<>();
        if (root==null){
            return null;
        }
       Stack<TreeNone> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNone none= stack.peek();
            if (none.right==null&&none.left==null){
                result.add(stack.pop().val);
            }
            if (none.right!=null){
                stack.push(none.right);
                none.right=null;
            }
            if (none.left!=null){
                stack.push(none.left);
                none.left=null;
            }
        }
        return result;
    }
    //视觉
    public static List<Integer> postOrder2(TreeNone root){
        List<Integer> result = new ArrayList<>();
        if (root==null){
            return null;
        }
        Queue<TreeNone> queue= new LinkedList<>();
        queue.add(root);
        Boolean right=false;
        while (!queue.isEmpty()){
            right=false;
        for (int i=0;i<queue.size();i++){
            TreeNone none = queue.poll();
            if (!right){
                result.add(none.val);
                right=true;
            }

            if (none.right!=null){
                queue.offer(none.right);

            }  if  (none.left!=null){
                queue.offer(none.left);
            }
        }}
        return result;
    }


}
